package 简单.模拟;

import java.util.Arrays;

/**
 * 学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照 非递减 的高度顺序排成一行。
 * 排序后的高度情况用整数数组 expected 表示，其中 expected[i] 是预计排在这一行中第 i 位的学生的高度（下标从 0 开始）。
 * 给你一个整数数组 heights ，表示 当前学生站位 的高度情况。heights[i] 是这一行中第 i 位学生的高度（下标从 0 开始）。
 * 返回满足 heights[i] != expected[i] 的 下标数量 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/height-checker
 */
public class 高度检查器_1051 {

    public static void main(String[] args) {

        int[] heights = {1, 1, 4, 2, 1, 3};
        System.out.println(heightChecker2(heights));

    }

    public int heightChecker(int[] heights) {
        int count = 0;
        int[] expected = new int[heights.length];
        System.arraycopy(heights, 0, expected, 0, expected.length);
        Arrays.sort(expected);
        for (int i = 0; i < expected.length; i++) {
            if (expected[i] != heights[i]) count++;
        }
        return count;
    }

    /**
     * 计数排序
     * 1 <= heights[i] <= 100，数字范围小
     *
     * @param heights
     * @return
     */
    public static int heightChecker2(int[] heights) {
        int count = 0;
        int[] expected = new int[101];
        for (int i = 0; i < heights.length; i++) {
            expected[heights[i]]++;
        }
        int expectedIdx = 1;
        for (int i = 0; i < heights.length; i++) {
            while (expectedIdx < expected.length && expected[expectedIdx] <= 0) expectedIdx++;
            if (expectedIdx != heights[i]) count++;
            expected[expectedIdx]--;
        }
        return count;
    }

}
